#define _CRT_SECURE_NO_WARNINGS 


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;


typedef BTNode* QDataType;



// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;


// 初始化队列
void QueueInit(Queue * q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->_front = NULL;
	q->_rear = NULL;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("进入失败\n");
		exit(-1);
	}
	newnode->_data = data;
	newnode->_next = NULL;
	if (q->_front == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
}

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);

	if (q->_front == NULL)
	{
		return;
	}
	Queue* tmp = q->_front->_next;
	free(q->_front);
	q->_front = tmp;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_front != NULL);
	return q->_front->_data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	return q->_rear->_data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	int size = 0;
	QNode* cur = q->_front;
	while (cur)
	{
		cur = cur->_next;
		size++;
	}
	return size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->_front == NULL;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
	if (q->_front == NULL) return;
	while (q->_front) QueuePop(q);
}


// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) //*pi 表示数组下标
{
	assert((*pi) < n);
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}

	//分配空间
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));

	root->_data = a[(*pi)++];

	root->_left = BinaryTreeCreate(a, n, pi);
	root->_right = BinaryTreeCreate(a, n, pi);

	return root;
}



// 层序遍历
//想法：先是根进去
//根出来，然后带进它的儿子 上一层带下一次层
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);//将根节点入队列

	while (!QueueEmpty(&q))//队列为空，层序遍历结束
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);

		//打印空数据
		if (cur)
		{
			printf(" %c", cur->_data);
			QueuePush(&q, cur->_left);
			QueuePush(&q, cur->_right);
		}
		//else printf("# ");

	}

	QueueDestroy(&q);
}


int main()
{
	int m = 0;
	BTDataType a[105];
	scanf("%s", a);
	int n = sizeof(a) / sizeof(char);
	BTNode* root = BinaryTreeCreate(a, n, &m);

	BinaryTreeLevelOrder(root);

	//BinaryTreeDestory(&root);

	return 0;
}


